package lc.q101_150;

import lc.TreeNode;

public class Q124 {

    private int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGame(root);
        return max;
    }

    public int maxGame(TreeNode root) {
        // 包含当前值的最大路径和
        if (root == null) {
            return 0;
        }
        // 左右节点和
        int left = Integer.max(0, maxGame(root.left));
        int right = Integer.max(0, maxGame(root.right));
        max = Integer.max(max, root.val + left + right);
        return root.val + Integer.max(left , right);
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(-10);
        treeNode.left = new TreeNode(9);
        treeNode.right = new TreeNode(20);
        treeNode.right.left = new TreeNode(15);
        treeNode.right.right = new TreeNode(7);
        System.out.println(new Q124().maxPathSum(treeNode));
    }
}
